#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pb push_back
#define y1 y_alpha_1

using namespace std;

using ll = long long;
using db = double;
using vec = vector<int>;
using pii = pair<int,int>;

int read() {
	int x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-',ch = getchar();
	while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
	return f ? -x : x;
}

const int N = 2e5+10;

int fa[N],n,Q,d[N];
ll ans;
struct edge{int a,b,w;};
bool operator < (edge a,edge b) {return a.w < b.w;}
vector <edge> e;

int gf(int x) { return fa[x] == x ? x : fa[x] = gf(fa[x]);}

bool merge(int x,int y) {
	x = gf(x),y = gf(y); if(x == y) return 0;
	return fa[x] = y,1;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,Q = in; for(int i = 1;i <= n;i++) fa[i] = i;
	memset(d,0x3f,sizeof d);
	for(int i = 1;i <= Q;i++) {
		int a = in,b = in,c = in;
		e.pb((edge){a,b,c});
		d[a] = min(d[a],c + 1);
		d[b] = min(d[b],c + 2);
	}
	for(int i = 0;i < n;i++) d[i] = min(d[i],d[(i - 1 + n) % n] + 2);
	for(int i = 0;i < n;i++) d[i] = min(d[i],d[(i - 1 + n) % n] + 2);
	for(int i = 0;i < n;i++) e.pb((edge){i,(i + 1) % n,d[i]});
	sort(e.begin(),e.end());
	for(auto x : e) 
		if(merge(x.a,x.b)) ans += x.w;
	printf("%lld\n",ans);
	return 0;
}
